home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-02 / sortdemo.zip / SDSORT04.INC < prev    next >
Text File  |  1992-04-15  |  5KB  |  122 lines
  1. (*
  2. ╔═══════════════════════════════════════════════════════════════════════════╗
  3. ║ Turbo Pascal 6.0 Include File : SDSORT04.INC                              ║
  4. ╟───────────────────────────────────────────────────────────────────────────╢
  5. ║ Program : SORTDEMO.PAS                                                    ║
  6. ╟───────────────────────────────────────────────────────────────────────────╢
  7. ║ Version : 1.0                                                             ║
  8. ╟───────────────────────────────────────────────────────────────────────────╢
  9. ║ Copyright (c) 1992  by  Jon S. Russell                                    ║
  10. ╟───────────────────────────────────────────────────────────────────────────╢
  11. ║ Merge sort routine for SORTDEMO.PAS                                       ║
  12. ╚═══════════════════════════════════════════════════════════════════════════╝
  13.                                                                            *)
  14. procedure MergeSort (var Info : InfoType;
  15.                          First : IndexType;
  16.                          Last  : IndexType);
  17. var
  18.   Middle : IndexType;  (* middle index in range to sort *)
  19.  
  20.   (*───────────────────────────────────────────────────────────────────────*)
  21.  
  22.   procedure MergeTogether (var Info       : InfoType;
  23.                                LeftFirst  : IndexType;
  24.                                LeftLast   : IndexType;
  25.                                RightFirst : IndexType;
  26.                                RightLast  : IndexType);
  27.  
  28.     (* Merge the two sorted subarrays, List[LeftFirst] ..     *)
  29.     (* List[LeftLast] and List[RightFirst] .. List[RightLast] *)
  30.     (* into a single sorted subarray, List[LeftFirst] ..      *)
  31.     (* List[RightLast].                                       *)
  32.  
  33.   var
  34.     Temp      : InfoType;    (* auxiliary array        *)
  35.     Index     : IndexType;   (* index into Temp        *)
  36.     SaveFirst : IndexType;   (* saves left first index *)
  37.  
  38.   begin  (* MergeTogether *)
  39.     (* Initialize indexes before the loop. *)
  40.     Index := LeftFirst;
  41.     SaveFirst := LeftFirst;
  42.  
  43.     Temp.xElems := Info.xElems;  (* for Swap procedure purposes only *)
  44.     Temp.yElems := Info.yElems;  (* for Swap procedure purposes only *)
  45.     Temp.Len    := Info.Len;     (* for Swap procedure purposes only *)
  46.  
  47.     (* Process while more elements are in both subarrays. *)
  48.     while (LeftFirst <= LeftLast) and
  49.           (RightFirst <= RightLast) do
  50.       begin
  51.         if (Info.List[LeftFirst].Key < Info.List[RightFirst].Key)
  52.           then
  53.             begin  (* copy from left half into Temp *)
  54.               Temp.List[Index] := Info.List[LeftFirst];
  55.               ShowBlock(Temp, Index);
  56.               Inc(LeftFirst);
  57.             end    (* Left element is smaller *)
  58.           else
  59.             begin  (* copy from right half into Temp *)
  60.               Temp.List[Index] := Info.List[RightFirst];
  61.               ShowBlock(Temp, Index);
  62.               Inc(RightFirst);
  63.             end;   (* Right element is smaller or equal. *)
  64.         Inc(Index);
  65.       end; (* while -- more elements in loop *)
  66.  
  67.     (* Copy any remaining elements from left half. *)
  68.     while (LeftFirst <= LeftLast) do
  69.       begin
  70.         Temp.List[Index] := Info.List[LeftFirst];
  71.         ShowBlock(Temp, Index);
  72.         Inc(LeftFirst);
  73.         Inc(Index);
  74.       end; (* while -- more elements in left half *)
  75.  
  76.     (* Copy any remaining elements from right half. *)
  77.     while (RightFirst <= RightLast) do
  78.       begin
  79.         Temp.List[Index] := Info.List[RightFirst];
  80.         ShowBlock(Temp, Index);
  81.         Inc(RightFirst);
  82.         Inc(Index);
  83.       end; (* while -- more elements in right half *)
  84.  
  85.     (* Copy the sorted elements from Temp back into List. *)
  86.     for Index := SaveFirst to RightLast do
  87.       begin
  88.         Info.List[Index] := Temp.List[Index];
  89.         ShowBlock(Info, Index);
  90.       end; (* for *)
  91.   end;   (* MergeTogether *)
  92.  
  93.   (*───────────────────────────────────────────────────────────────────────*)
  94.  
  95. begin  (* MergeSort *)
  96.   Info.Sorted := false;  (* reset flag *)
  97.  
  98.   (* Base Case: Check for empty list or single element. *)
  99.   if First < Last then
  100.     begin  (* General Case *)
  101.       (* Cut the array into two halves. *)
  102.       Middle := (First+Last) div 2;
  103.  
  104.       (* Sort the left subarray. *)
  105.       MergeSort(Info, First, Middle);
  106.  
  107.       (* Sort the right subarray. *)
  108.       MergeSort(Info, Middle+1, Last);
  109.  
  110.       (* Merge the two sorted halves together. *)
  111.       MergeTogether(Info,      (* array to sort              *)
  112.                     First,     (* first index in left half.  *)
  113.                     Middle,    (* last index in left half.   *)
  114.                     Middle+1,  (* first index in right half. *)
  115.                     Last);     (* last index in right half.  *)
  116.     end;  (* General Case *)
  117.  
  118.   Info.Sorted := true;  (* set flag *)
  119. end;   (* MergeSort *)
  120.  
  121. (*─────────────────────────────────────────────────────────────────────────*)
  122.